1. Field of the Invention
The invention relates to a survivor path memory circuit, and more particularly to a survivor path memory circuit used in a Viterbi decoder, in which the registers of survivor paths are replaced with the registers of decision bit paths so that the memory requirement for the survivor path memory circuit is reduced.
2. Description of the Related Art
A PRML (Partial Response Maximum Likelihood) system is used to retrieve EFM (Eight-to-Fourteen Modulation) signals from CD (Compact Disc)/DVD (Digital Versatile Disk). In the PRML system, a Viterbi decoder is usually used to realize the maximum likelihood detection.
FIG. 1 is a block diagram showing a conventional Viterbi decoder. Referring to FIG. 1, the Viterbi decoder includes a branch metric generator 11, an add-compare-select (ACS) unit 12, a survivor path memory circuit 13, and a decoding unit 14. The branch metric generator 11 calculates the branch metrics corresponding to each branch according to the received data, and outputs branch metrics to the ACS unit 12. The branch metric generator 11 calculates the distance, such as mean-square-distance, between the received data and the estimated data of the branch. For each state, the ACS unit 12 adds the branch metrics with the related state metrics to generate the candidate state metrics, compares and selects the minimum candidate state metric as the new state metric. The decision bit of the ACS unit 12, indicating the decision result of the state-metric selection, is sent to the survivor path memory circuit 13. According to the decision bit, the survivor paths of the survivor path memory circuit 13 are updating to keep consistent with the selected result of related state metrics. The survivor memory circuit 13 restores the decoded results corresponding to each state, and the decoding unit 14 executes the majority vote for the ending bits of all survivor paths to decide the decoded result.
FIG. 2 is a data flow chart (DFC) of a conventional two-state trellis diagram for a survivor path memory circuit. As shown in FIG. 2, a plurality of registers D are employed to store the output value generated from the multiplexers Mux and output data to the multiplexers of next stage. Each decision bit of the ACS unit 12 is simultaneously connected to all the multiplexers of a set of survivor path in order to select the multiplexer's signal.
In the CD/DVD application, the recording signal with EFM/EFM+modulation, called the EFM signal, has the property of run length limited (RLL) that the minimum run length of an EFM signal is 3T, where T is a recording unit length. According to the RLL of the EFM signal, a simplified trellis diagram is obtained to build a PRML system for decoding the EFM signal, as shown in FIG. 3. The trellis diagram in FIG. 3 has six states, including state S0(000), state S1(001), state S2(011), state S3(100), state S4(110), and state S5(111). The states of (010) and (101) are invalid and not listed due to the minimum run length of 3T. In addition, state S1(001), state S2(011), state S3(100) and state S4(110) only have a branch.
FIG. 4 is a block diagram showing a part of the Viterbi decoder using the trellis diagram of FIG. 3. Referring to FIG. 4, the Viterbi decoder includes an ACS unit 22, a survivor path memory circuit 13, and a decoding unit 14. Since the trellis diagram has been simplified, the ACS unit 22 only includes two ACS processors 221 and 222, two adders 231, 232, and six registers 225 to 230. Also, since the trellis diagram has been simplified, only the survivor paths 0 and 5 in the survivor path memory circuit 13 include multiplexers, and data from other survivor paths 1 to 4 are just delayed by the registers and then transferred to another survivor path memory or multiplexers. Each stage of the survivor path memory circuit 13 related to one decoding cycle contains six registers to store the output values generated from the multiplexers in the survivor path memory circuit 13, in which the number of register equals to the number of the state in the trellis, where a decoding cycle means that the Viterbi decoder decodes 1 bit data. The decoding unit 14 utilizes a majority vote circuit to vote, among the data output from the six paths, the majority data as the decoded data.
FIG. 5 is a data flow chart showing the survivor path memory circuit of FIG. 4, where a node means an operation and an edge means a connection with the delay latency labeled on it. As shown in FIG. 5, the survivor path memory circuit includes a plurality of multiplexers Mux and registers (path memory) D, 2D and 3D, wherein each of the registers D represents a register that is delayed by one decoding cycle (stage), each of the registers 2D represents a register that is delayed by two decoding cycles, and each of the registers 3D represents a register that is delayed by three decoding cycles. The two decision bits output from ACS unit 22 are inputted to the multiplexers of two sets of survivor paths of the survivor path memory circuit 13, respectively.
Since a memory is utilized to store data in each path within each cycle and the multiplexer in each path receives the same decision bit signal, the memory usage in each path may be effectively reduced if the timing of the selection signal for the multiplexers can be rearranged.